package top.fengleifeng.question;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Objects;

/**
 * @author : fengleifeng
 * @Package top.fengleifeng.question
 * @Description:
 * @date Date : 2021年01月07日 8:37 下午
 */
public class Num547省份数量 {

    class Solution {

        public int findCircleNum(int[][] isConnected) {
            if (isConnected.length <= 0) {
                return 0;
            }

            boolean[] booleans = new boolean[isConnected.length];
            int[] intNum = new int[isConnected.length];
            int count = 0;
            Map<Integer, List<Integer>> map = new HashMap<>();
            for (int i = 0; i < isConnected.length; i++) {
                for (int j = i; j < isConnected[i].length; j++) {
                    if (isConnected[i][j] == 1) {
                        if (booleans[j]) {//说明已经存过了
                            //把
                            Integer mapKeyI = intNum[i];
                            Integer mapKeyJ = intNum[j];
                            if (mapKeyI.intValue() != mapKeyJ.intValue()) {
                                setMap(mapKeyI, mapKeyJ, map, intNum);
                            }
                        } else {
                            Integer mapKey = getMapData(map, i);
                            if (Objects.isNull(mapKey)) {
                                count++;
                                List<Integer> mapValue = new LinkedList<>();
                                mapValue.add(j);
                                map.put(count, mapValue);
                                intNum[j] = count;
                            } else {
                                List<Integer> list = map.get(mapKey);
                                list.add(j);
                                intNum[j] = mapKey;
                            }
                        }
                        booleans[j] = true;
                    }
                }
            }
            return map.size();
        }

        private void setMap(Integer mapKeyI, Integer mapKeyJ, Map<Integer, List<Integer>> map, int[] intNum) {
            List<Integer> listI = map.get(mapKeyI);
            List<Integer> listJ = map.get(mapKeyJ);
            for (int i = 0; i < listJ.size(); i++) {
                intNum[listJ.get(i)] = mapKeyI;
            }
            listI.addAll(listJ);
            map.remove(mapKeyJ);
        }

        private Integer getMapData(Map<Integer, List<Integer>> map, int value) {
            for (Map.Entry<Integer, List<Integer>> one : map.entrySet()) {
                List<Integer> oneValue = one.getValue();
                if (oneValue.contains(value)) {
                    return one.getKey();
                }
            }
            return null;
        }
    }

    public static void main(String[] args) {
        int[][] ints = {{1, 1, 0}, {1, 1, 0}, {0, 0, 1}};
        int circleNum = new Num547省份数量().new Solution().findCircleNum(ints);
        System.out.println(circleNum);
    }

}
